package BSQX_Bit;

import java.util.HashSet;
import java.util.Scanner;

public class BSQX_4_25 {
    public static void main(String[] args) {
      Scanner in = new Scanner(System.in);

        int[] arr = new int[100001];
        int n = 0;
        arr[0] = 1;
        arr[1] = 1;
        for (int i = 2; i <= 100000; i++)
        {
            arr[i] = arr[i - 1] +arr[i - 2];
            arr[i] = arr[i] % 1000000;
        }
        while (in.hasNextInt()){
            //前面补0,要用06d
            n = in.nextInt();
            System.out.println(arr[n]);
        }

    }
    public static int func(int n){
        final int MOD = 1000000;
        if (n<2)return n;
        int a=1,b=1,r=0;
        for (int i = 1; i < n; i++) {
            r=(a+b)%MOD;
            a=b;
            b=r;
        }
        return r;
    }
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            String s1 = in.nextLine();

            HashSet<Integer> set =new HashSet<>();
            set.add(2);
            set.add(3);
            set.add(5);
            set.add(7);
            set.add(11);
            String[] strings1=s1.split(" ");

            int ret = fun(strings1,set);
            System.out.println(ret);


        }
    }
    public static int func(int d1,int d2,boolean flg){
        int sum=0;
        if (flg){
            //说明是月份为素数
            sum = d2-d1+1;
        }else {
            sum=(d2-d1+1)*2;
        }
        return sum;
    }
    public static int fun(String[] s1,HashSet<Integer> set){
        int year1=Integer.parseInt(s1[0]);
        int year2=Integer.parseInt(s1[3]);
        int m1 =Integer.parseInt(s1[1]);
        int m2 =Integer.parseInt(s1[4]);
        int d1=Integer.parseInt(s1[2]);
        int d2=Integer.parseInt(s1[5]);
        //将年份与天数都拿出来
        //定义月份数组
        int[] ms={31,28,31,30,31,30,31,31,30,31,30,31};

        boolean flag1 = (year1%4==0&&year1%100!=0)||(year1%400==0)?true:false;//第一年是不是闰年
        boolean flag2 = (year2%4==0&&year2%100!=0)||(year2%400==0)?true:false;//第二年是不是闰年

        int sum=0;//求和

        if (year1 == year2){
          //年相等的情况
            if (m1 == m2){
                //月份一样的情况下
                boolean flag =set.contains(m1)?true:false;
                return func(d1,d2,flag);
            }else {
                //月份不一样的情况下
                boolean sZ;//判断当月是不是素数
                for (int i = m1+1; i < m2 ; i++) {
                    if (m1 == 2 && flag1){
                        ms[1]+=ms[1]+1;//2月天数加1
                    }
                   sZ=set.contains(i)?true:false;
                    sum += func(1,ms[i-1],sZ);
                }
                sZ=set.contains(m2)?true:false;//处理终止月的情况
                sum += func(1,d2,sZ);
                sZ=set.contains(m1)?true:false;
                sum += func(d1,ms[m1-1],sZ);//处理起始月的情况
            }
        }else {
           //年不一样的情况下,要遍历每一年

            for (int i = year1+1; i < year2; i++) {
                boolean flag =(i%4==0&&i%100!=0)||(i%400==0)?true:false;
                if (flag)sum+=551+29;
                else sum+=551+28;
            }
            if (year2 == 2999)sum-=28;

            boolean sZ;
            //第一年
            for (int i = m1+1; i <= 12; i++) {
                if (i == 2 && flag1){
                    ms[1]+=ms[1]+1;//2月天数加1
                }
                //处理起始月
                sZ=set.contains(i)?true:false;
                sum += func(1,ms[i-1],sZ);//数组是从0开始的
            }

            sZ=set.contains(m1)?true:false;
            sum += func(d1,ms[m1-1],sZ);//处理起始月的情况

            //最后一年的情况
            ms[1] = 28;//重置2月天数
            for (int i = 1; i < m2; i++) {
                if (i == 2 && flag2){
                    ms[1]+=ms[1]+1;//2月天数加1
                }
                sZ=set.contains(i)?true:false;
                sum += func(1,ms[i-1],sZ);
            }
            sZ=set.contains(m2)?true:false;//处理终止月的情况
            sum += func(1,d2,sZ);

        }
        return sum;
    }
}
